The red fox (Vulpes vulpes) has the widest global distribution among terrestrial carnivore species, occupying most of the Northern Hemisphere in its native range. Because it carries diseases that can be transmitted to humans and domestic animals, it is important to gather information about their movements and dispersal in their natural habitat but it is difficult to do so at a broad scale with trapping and telemetry. In this study, we have described the genetic diversity and structure of red fox populations in six areas of north-eastern Poland, based on samples collected from 2002–2003. We tested 22 microsatellite loci isolated from the dog and the red fox genome to select a panel of nine polymorphic loci suitable for this study. Genetic differentiation between the six studied populations was low to moderate and analysis in Structure revealed a panmictic population in the region. Spatial autocorrelation among all individuals showed a pattern of decreasing relatedness with increasing distance and this was not significantly negative until 93 km, indicating a pattern of isolation-by-distance over a large area. However, there was no correlation between genetic distance and either Euclidean distance or least-cost path distance at the population level. There was a significant relationship between genetic distance and the proportion of large forests and water along the Euclidean distances. These types of habitats may influence dispersal paths taken by red foxes, which is useful information in terms of wildlife disease management.